package test;

import java.util.LinkedList;

/**
 * @author sunzhuokun
 * @date 11:09 2024/5/15
 * @description 解压报文
 * 为了提升数据传输的效率，会对传输的报文进行压缩处理。输入一个压缩后的报文，请返回它解压后的原始报文。
 * 压缩规则：n[str]，表示方括号内部的 str 正好重复 n 次。注意 n 为正整数（0 < n <= 100），str只包含小写英文字母，不考虑异常情况。
 * " “输入描述:
 * 输入压缩后的报文：
 * 1）不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的；
 * 2）原始报文不包含数字，所有的数字只表示重复的次数 n ，例如不会出现像 5b 或 3[8] 的输入；
 * 输出描述:
 * 解压后的原始报文
 * 注：
 * 1）原始报文长度不会超过1000，不考虑异常的情况
 * 示例1
 * 输入
 * 3[k]2[mn]
 * 输出
 * kkkmnmn
 * 说明
 * k 重复3次，mn 重复2次，最终得到 kkkmnmn
 * 示例2
 * 输入
 * 3[m2[c]]
 * 输出
 * mccmccmcc
 * 说明
 * m2[c] 解压缩后为 mcc，重复三次为 mccmccmcc”
 */
public class DecompressionMessage_解压报文 {

    public static void main(String[] args) {
//        String input = "3[m2[c]]";
        String input = "3[k]10[mn]";
//        String input = "3[k]ljk2[mn]";
        System.out.println(decompress(input));
    }

    private static String decompress(String input) {
        LinkedList<Integer> numQueue = new LinkedList<>();
        LinkedList<String> strQueue = new LinkedList<>();
        int end = 0;
        int countStart = 0;
        StringBuilder res = new StringBuilder();
        String subRes = "";
        for (int start = 0; start < input.toCharArray().length; start++) {
            char c = input.charAt(start);
            if (Character.isDigit(c)) {
                // 需要向后找到不是数字的字符
                StringBuilder numSb = new StringBuilder();
                while (Character.isDigit(input.charAt(start))) {
                    numSb.append(input.charAt(start));
                    start++;
                }
                numQueue.push(Integer.parseInt(numSb.toString()));
                start--;
                continue;
            }
            if (Character.isLetter(c)) {
                numQueue.push(1);
                strQueue.push(String.valueOf(c));
                continue;
            }
            if (c == '[') {
                end = start + 1;
                countStart++;
                // 找到end
                while (countStart != 0 && end < input.length()) {
                    if (input.charAt(end) == '[') {
                        countStart++;
                    } else if (input.charAt(end) == ']') {
                        countStart--;
                    }
                    end++;
                }
                subRes = decompress(input.substring(start + 1, end - 1));
                // 更新start
                start = end - 1;
                strQueue.push(subRes);
            }

            if (end == input.length()) {
                break;
            }
        }

        while (numQueue.size() != 0) {
            Integer len = numQueue.pollLast();
            String subStr = strQueue.pollLast();
            for (int i = 0; i < len; i++) {
                res.append(subStr);
            }
        }

        return res.toString();
    }
}
